#include<vector>
using namespace std;

class Solution {
private:
    int dist(const vector<int>point) {
        return point[0] * point[0] + point[1] * point[1];
    }
    void swapMedia(vector<vector<int>>& vec, int left, int right, int mid) {
        if (vec[left][1] < vec[right][1]) {
            if (vec[left][1] > vec[mid][1])
                swap(vec[left], vec[mid]);
        }
        else {
            if(vec[right][1]< vec[mid][1])
                swap(vec[left], vec[right]);
            else
                swap(vec[left], vec[mid]);
        }
    }

    void nthElement(vector<vector<int>>& vec, int k) {
        if (k > vec.size()) return;
        int start = 0, end = vec.size();
        while (start<end) {
            swapMedia(vec, start, end - 1, start + (end - start) / 2);
            int povit = start;
            int left = start + 1, right = end - 1;
            while (left <= right) {
                while (left <= right && vec[left][1] <= vec[povit][1]) ++left;
                while (left <= right && vec[right][1] > vec[povit][1]) --right;
                if (left <= right)
                    swap(vec[left], vec[right]);
            }
            swap(vec[right], vec[povit]);
            if (right < k) start = right + 1;
            else if (right > k) end = right;
            else break;
        }
    }

public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        vector<vector<int>> vec;
        if (K == 0) return vec;
        for (int i = 0; i < points.size(); ++i) {
            vec.push_back({ i, dist(points[i])});
        }
        nthElement(vec, K - 1);
        vector<vector<int>> res(K);
        for (int i = 0; i < res.size(); ++i) {
            res[i]=points[vec[i][0]];
        }
        return res;
    }
};
//int main() {
//    vector<vector<int>> points = { {1,3},{-2,2} };
//    Solution sol;
//    sol.kClosest(points, 1);
//}